% \begin{itemize}
% \item define ULslot and UBslot
% \item show how we can deal with each region separately.
% \end{itemize}

%\subsection{Pessimism in the previous analysis}

As seen in Section~\ref{ssec:task_request_profiles}, in order to determine the memory-profile of the tasks, we temporally divided the execution of each task into a sequence of sampling regions for which we derived a lower and upper bound on the number of requests that can be issued. However, in Algorithm~\ref{algo:MaxDelay}, we did not leverage all these region-specific memory profiles as we used the quantity $\NbReqPerTask{i}$ only. Algorithm~\ref{algo:MaxDelay} views the input task $\tau_i$ as a single region that can issue up to $\NbReqPerTask{i}$ requests. As a consequence, the resulting analysis may lead to pessimistic upper bounds as illustrated in the following example.

\begin{footnotesize}
\begin{Example}
As a simple example, consider that a task issues 10 requests and there are 500 potential free slots, such that slots numbered [491 to 500] contribute to the 10 highest delays. 
Then a single-region based approach will assign all the 10 requests to slots [491 to 500].
Next, assume we break the task into 2 regions and find that there are 7 requests in Region~1 and 3 requests in Region~2.
Likewise, we also compute that the first 300 slots are feasibly available for region 1 and the next 200 slots are available for Region~2.
Then the resulting analysis can be tighter, since it will assign the 7 requests to the slots (with the 7 highest delays) from these 300 slots and the 3 requests to 3 slots from 491 to 500.
\end{Example}
\end{footnotesize}
 
Although the exact intervals of the arrivals of these requests are difficult to discern, if it is possible to divide the task into regions and derive the upper bound on the requests in each region, then likewise we can find an upper bound on the range of slots that can be potentially available to the requests of a given region. In the absence of such demarcations, requests may be assigned to unfeasible slots, leading to pessimistic outcomes. 

Thus, the advantages of region-based analysis are twofold: Firstly, they decrease the computation time by limiting the number of possible candidate slots that must be explored and secondly, they lead to tighter analysis by discarding a considerable amount of unfeasible solutions. We proceed by elaborating on the theoretical foundations of region-based analysis, followed by a detailed description of the algorithm.
 
% \subsection{Computation of LBslot and UBslot}
% As mentioned earlier in Section~\ref{sec:probdef}, we define a range $[\LBslot{i}{k}, \UBslot{i}{k}]$ 
% for each region $k$, where $\LBslot{i}{k}$ and $\UBslot{i}{k}$ are the first and last free bus slots in which a request from region $k$ can be served, respectively.
% In  order to restrict the analysis time to a safe value, it therefore necessary to first compute a coarse upper-bound $\UBTime{i}{k}$, on the execution time of task $\tau_i$ which is provably safe (even if largely pessimistic). 
% %This implies that in any case, the task will not execute beyond that time.
% By construction, $\Tmax{i}{1}$ is the longest waiting time for one request before which it can be assigned a free bus slot\footnote{This is because the underlying algorithm to compute this value (see~\cite{Icess12} for details) considers the ordering of tasks in the core to issue the maximum requests in a given time interval}.
% This value can be computed considering the entire task $\tau_i$ as a single region with $\NbReqPerTask{i}$ requests as follows:
% \begin{equation}
% \TaskUBTime{i} \leftarrow \min( D_i, C_i +  \NbReqPerTask{i} \times \Tmax{i}{1}) 
% \label{eq:ubtime}
% \end{equation}
% To compute the upper bound, Equation~\ref{eq:ubtime} assumes that all the requests of task $\tau_i$ incur this waiting delay and assigns it to UBtime.
%  Since the deadline of a task inherently limits the execution time, UBTime is restricted to the minimum of the apriori computed value and the deadline.
%  Given this coarse upper bound, the $\Tmin{i}{x}$ and $\Tmax{i}{x}$ values for all the slots which may be available upto $\TaskUBTime{i}$ are computed. 
% \begin{enumerate}
%  \item Compute $\Tmax{i}{x}$, $\forall x$ such that $\Tmax{i}{x} \leq \TaskUBTime{i} $ using Equation~\ref{eq:tmax}
%  \item  $ \TaskUBslot{i} \leftarrow \max_{x > 0} \{ x \mid \Tmax{i}{x} \leq  \TaskUBTime{i} \} $
%  \item Compute $\Tmin{i}{x}$, $\forall x \in 1 \dots \TaskUBslot{i}$ using Equation~\ref{eq:tmin} 
% \end{enumerate}
% For a task-wise analysis, we can safely assume $\TaskLBslot{i}$=1.
% The requests may now be assigned to slots in the range [1, $\TaskUBslot{i}$]. It is important to remember that this $\TaskUBTime{i}$ is a very coarse upper bound and the 
% resulting increased WCET in contention $C_i'$ derived via the algorithm should lie between $C_i$ and $\TaskUBTime{i}$, i.e., $C_i \leq C_i' \leq \TaskUBTime{i}$. 

%\subsection{Multiple Sampling Region Analysis}


\subsection{Theoretical Foundation}
When a task is divided into regions and runs in conjunction with other tasks, the time at which each of its regions starts executing depends on the delays incurred by the requests issued in its previous regions. The following lemmas express the relation that exist between the starting time of a region and the maximum delay that it can incur. These properties allow for a fine-tuned WCET analysis in which the distribution of requests across regions is exploited to obtain region-accurate estimates. 

\begin{lemma}
\label{lem:anomaly}
Consider two execution scenarios of a task $\tau_i$ of region $k$. In the first scenario, region $k$ starts executing at time $t_1$, whereas in the second scenario region $k$ starts executing at time $t_2$ and $t_1 < t_2$. It may happen that the maximum delay that region $k$ can possibly incur in Scenario~1 is higher than the delay incurred in Scenario~2.
\begin{proof}
We prove the claim by using a simple example. Let us consider the functions $\Tmin{i}{\cdot}$ and $\Tmax{i}{\cdot}$ depicted in Figure~\ref{fig:anomaly} and assume that $\NbReqPerRegion{i}{k} = 2$. By starting at time $t_2$ the maximum delay that region $k$ can incur is given by $\Delta_2 + \Delta_3$ while it can be seen that, by starting at time $t_1$, the maximum delay is $\Delta_1 + \Delta_2 > \Delta_2 + \Delta_3$. 
\end{proof}
\end{lemma}


\begin{figure}[t]
\centering
\includegraphics*[scale=0.25]{figures/anomaly-crop.pdf}
\caption{Notations used in proof of Lemma~\ref{lem:anomaly}}
\label{fig:anomaly}
\end{figure}

\begin{figure}[t]
\centering
\includegraphics*[width = 1\textwidth, viewport = 0 0 2000 350]{figures/scenarios.pdf}
\caption{Notations used in proof of Lemma~\ref{lem:latest_finish_time}}
\label{fig:latest_finish_time}
\end{figure}

\begin{lemma}
\label{lem:latest_finish_time}
Although Lemma~\ref{lem:anomaly} holds and the delay incurred by executing at time $t_1$ may be greater than the delay incurred at time $t_2$ $(>t_1)$, the finishing time of region $k$ can never be higher if the task executes at time $t_1$. Informally, the extra delay that region $k$ may incur in Scenario~1 by starting earlier does not make up for the difference of starting time between the two scenarios.

% 
% 
% \begin{lemma}
% \label{lem:latest_finish_time}
% Despite the previous result, it can also be shown that the finishing time of region $k$ can never be higher in scenario 1 than in Scenario~2, i.e. the extra delay that region $k$ may incur in Scenario~1 by starting earlier does not make up for the difference of starting time between the two scenarios.
\begin{proof}
The proof is obtained by contradiction. Let us denote by $f_1$ and $f_2$ the finishing time of region $k$ in Scenario~1 and~2, respectively. By contradiction, assume that $f_1 > f_2$. Figure~\ref{fig:latest_finish_time} illustrates these two scenarios: an ``X'' represents the release of a request, a continuous line represents the execution of the region, and a dashed line is an interval of time during which the task stalls, waiting for a request to be served. It is assumed in this illustration that region $k$ generates a maximum of $\NbReqPerRegion{i}{k} = 4$ requests.

Let $D_1$ and $D_2$ denote the \emph{maximum delay} that region $k$ can incur in Scenarios~1 and~2, respectively. There are two cases: if $D_1 \leq D_2$, we have $f_1 = \SamplingRegionSize{i} + D_1$ and $f_2 = \SamplingRegionSize{i} + D_2$ and it thus holds that $f_1 < f_2$, which contradicts our assumption. Otherwise, if  $D_1 > D_2$, suppose that region $k$ incurs the maximum delay of ($t_2 - t_1$) during the time-interval $[t_1, t_2]$, with a single request generated upon beginning its execution. The delay incurred by this single request can even extend until time $t_3 > t_2$, as depicted in Figure~\ref{fig:latest_finish_time}. This scenario can easily be shown to be a worst case (with respect to the finishing time), as it generates the maximum delay with the fewest requests, thereby delaying the actual workload of $\SamplingRegionSize{i}$ units of execution as much as possible. Now, let us denote by $\{ \Assignment{i}{2}, \ldots, \Assignment{i}{\NbReqPerRegion{i}{k}} \}$ the free-bus-slot assignment of 
the $(\NbReqPerRegion{i}{k} - 1)$ last requests of region $k$ in Scenario~1 (note that, unlike what is depicted on Figure~\ref{fig:latest_finish_time}, the free-bus-slot assignment of these requests may be the same as in Scenario~2). We can create a third scenario, in which region $k$ starts its execution at time $t_2$ (as in Scenario~2) and such that the first request is released upon beginning its execution, thereby incurring the same delay between $[t_2, t_3]$ as in Scenario~1, and all the subsequent requests follow the same free-bus-slot assignment as in Scenario~1, thereby incurring again the same delay as in Scenario~1. In this new Scenario~3, it thus holds that region $k$ starts at time $t_2$ and finishes at time $f_3 = t_2 + D_3 = f_1 > f_2 = t_2 + D_2$, which contradicts our initial assumption defining $D_2$ as the maximum delay that region $k$ can incur when starting at time $t_2$.
\end{proof}
\end{lemma}

To summarize, an important inference from Lemma~\ref{lem:latest_finish_time} is that the WCET of a task (considering contention) can be determined by computing the worst-case finishing time $f_1$ of its first region, and then iterating over the subsequent regions, assuming for each region $k$, a starting time of $f_{k-1}$. The WCET of the entire task is then given by the worst-case finishing time $f_{w_i}$ of its last region $w_i = \frac{C_i}{\SamplingRegionSize{i}}$.


\subsection{Algorithm Description}
With Algorithm~\ref{alg:regAnalysis}, we propose an arbiter-independent method to determine the worst-case cumulative delay.
Since the input to this algorithm is the $\Tmin{i}{.}, \Tmax{i}{.}$ functions and the details of the analyzed task,
any arbiter for which these values can be determined can leverage this algorithm.

The algorithm commences by computing the number $w_i$ of regions (Line~1) and then considers each region $k$ successively (Line~2).
Next, given the number $\NbReqPerRegion{i}{k}$ of requests in the analyzed region $k$, it finds a \emph{coarse} upper bound on its increased execution time $\UBTime{i}{k}$ assuming that each request in region $k$ may incur a delay of $\Tmax{i}{1}$.  Then, it computes the range of the slots that the requests of region $k$ may occupy (Lines 5-6), assuming on Line~5 a starting time of $f_{i, k-1}$. 

%When run in isolation the requests of a given region have immediate access to the memory, while with contention, 
%the requests incur a delay, causing the region to \emph{stretch in time} and the requests to be spaced apart. 
To compute the worst-case delay of each region, the algorithm invokes a slightly modified version of Algorithm~\ref{algo:MaxDelay} in which (i) $j$ now spans from $k + \LBslot{i}{k}$ to $\UBslot{i}{k} - (\NbReqPerRegion{i}{k} - k)$) on Line~4, (ii) the 2D array contains $\UBslot{i}{k} - \LBslot{i}{k}$ columns, (iii) all the references to a cell $c(k,j)$ are replaced with a reference to cell $c(k,j - \LBslot{i}{k})$, and (iv) references to $C_i$ are substituted for references to $\SamplingRegionSize{i}$. Note that a task modeled as a single region is a special case in which $\LBslot{i}{1} = 1$, the region size $\SamplingRegionSize{i}$ is $C_i$, and the maximum number of requests is $\NbReqPerTask{i}$. The delay of the currently analyzed region $\delta_{i,k}$ is computed on Line~7 and is then accounted for in the worst-case finishing time $f_{i,k}$ computed on Line~8. The process is repeated for all the regions and the finishing time of the last region gives the increased WCET of the task.

\begin{algorithm}[h!]
\scriptsize
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{$\tau_i$,$\Tmin{i}{.}, \Tmax{i}{.}$ } 
\Output{WCET of $\tau_i$ (considering contention)} 
$w_i = \frac{C_i}{\SamplingRegionSize{i}}$; $C_{i}' \leftarrow 0 $ \;
\For { region $k$ in task $\tau_i$ from $1$ to $w_i$}
{ 
  $\NbReqPerRegion{i}{k} \leftarrow$ No of requests in region $k$ \;
  $\UBTime{i}{k} \leftarrow f_{i,k-1} + \SamplingRegionSize{i} + \NbReqPerRegion{i}{k} * \Tmax{i}{1} $\;                                      
  \tcp{with $f_{i,0} = 0$}
  $\LBslot{i}{k} \leftarrow \min_{x > 0} \{ x \mid \Tmax{i}{x} \geq  f_{i,k-1} \} $\;
  $\UBslot{i}{k} \leftarrow \min_{x > 0} \{ x \mid \Tmin{i}{x} \geq  \UBTime{i}{k} \} $\;   
  $\delta_{i,k} = \MaxRegDelay (\NbReqPerRegion{i}{k}, \LBslot{i}{k},\UBslot{i}{k}) $\;
  $f_{i,k} = f_{i,k-1} + \SamplingRegionSize{i} + \delta_{i,k}$ \; 
}  
 \Return{$f_{i, w_i}$}\;
\caption{ComputeTaskWCET($\tau_i, \Tmin{i}{.}, \Tmax{i}{.}$)}
\label{alg:regAnalysis}   
\end{algorithm}
%\subsection{Computing the region bounds}

%The minimum time at which requests for a region $k$ can be served, $\LBTime{i}{k}$ is from the beginning of the region, given by the the term $(k-1) \times \SamplingRegionSize{i}$. The upper bound on the time upto which the requests of region $k$ can be served $\UBTime{i}{k}$, is the sum of the increased execution time $C_i'$ and the term $(\NbReqPerRegion{i}{k} - 1 ) * \Tmax{i}{1} $. To fix a coarse upper bound on the number of available slots, the method assumes that each request may incur a delay of $\Tmax{i}{1}$. However, depending on the memory traffic, many requests may incur lower delays (than $\Tmax{i}{1})$ and thus the computed $C_i'$ can be much lower than the coarse upper bound. The above range implies that requests of region $k$ can be scheduled in the the free bus slots slots during time interval [$\LBTime{i}{k}$, $\UBTime{i}{k}$]. Then, the lower and upper bound on the slots, $\LBslot{i}{k}$ and $\UBslot{i}{k}$  corresponds to the earliest slots for which LBTime and UBTime are greater or equal 
% to $\Tmin{i}{.}, \Tmax{i}{.}$ correspondingly.A task modeled as a single region is a special case in which $\LBslot{i}{1} = 1$ and all its requests $\NbReqPerTask{i}$ are considered to compute the upper bound on the last available slot. 

%Given this design, there may be overlapping candidate slots between two regions, leading to some pessimism, but determining the exact demarcation of free slots at design time is a non-trivial problem (especially for arbitration mechanisms that do not reserve slots). It is important to note that ignoring this overlap may also lead to unsafe estimates as potential slots contributing to the global maximum delays may be overlooked.









% Let us sketch the steps which form the basis of this optimized method. 
% Let us denote the increased sum as C_i
% \begin{enumerate}
% \item  Compute $\LBTime{i}$ and $UBTime $ for Region k 
% \item  Compute LBSlot and UBSlot for Region 1
% \item  Pass the parameters $\NbReqPerRegion{i}{1}$, 
% 
% \end{enumerate}
% 

% 
% \begin{enumerate}
%  \item 
%  Compute the time-bounds for region 1 as done in Equation~\ref{eq:ubtime}.
% \begin{equation}
% \UBTime{i}{1} \leftarrow \min( D_i, C_i +  \NbReqPerRegion{i}{1} \times \Tmax{i}{1}) 
% \label{eq:ubtimeregion1}
% \end{equation}
% For region 1 we set  $\LBslot{i}{1} = 1$ and we compute $\UBslot{i}{k}$ 
% $\LBtime^1 = 0$ and 
% \begin{equation}
% \UBTime{i}{1} = lenRegion + \Tmax{i}{1}  * \NbReqPerRegion{i}{k}  \nonumber 
% \end{equation}
% \item 
%  $\Tmin{i}{x}$, $\forall x \in 1 \dots \TaskUBslot{i}$ using Equation~\ref{eq:tmin} 
% Compute $\UBslot^1$ for region 1;
% \begin{equation}
% \UBslot^1 = \max_{x > 0} \{ x \mid \Tmax(x) \leq  \UBtime^1 \}\;
% \label{eq:ubslot}
% \end{equation}
% Therefore requests of region 1 will possibly take slots between [1, $\UBslot^1$];
% \item
% Let us denote the increased execution time of region~$r$ \emph{considering contention from other tasks} as $Cnew_i^{r}$.
% Run the naive algorithm over region 1 to compute the increased execution time  $Cnew_i^1$.
% \item 
% For the second region the coarse upper and lower bounds on the execution time, $[\LBtime^2, \UBtime^2]$ are given by
% \begin {equation}
% [C_i^1, Cnew_i^1 + C_i^2+ \Tmax(1)* Nrq^2] \nonumber
% \end {equation}
% Compute the $\LBslot$ and the $\UBslot$ for this region as done in Equation~\eqref{eq:ubslot}.
% Run the naive request to slot algorithm to determine the increased bounds for region~2 as $Cnew_i^2$.
% \item
% For region $r$ we compute $[\LBtime^r, \UBtime^r]$  by 
% \begin {equation}
% [\sum_{j=1}^{r-1}C_i^r, \sum_{j=1}^{r-1}Cnew_i^r + C_i^r+ \Tmax(1)* Nrq^r] \nonumber
% \end {equation}
% \end{enumerate}


